Orienteering Problems by Pieter Vansteenwegen & Aldy Gunawan

Author:Pieter Vansteenwegen & Aldy Gunawan
Language: eng
Format: epub
ISBN: 9783030297466
Publisher: Springer International Publishing

5.3.3 Metaheuristics for the TOP

Various types of solution algorithms are developed for solving the TOP, such as a memetic algorithm (MA), simulated annealing (SA), particle swarm optimization (PSO) and a genetic algorithm (GA). A memetic algorithm is a combination of an evolutionary algorithm and local search (LS) techniques and it has been used for solving the VRP. In the context of the TOP, a genetic algorithm (GA) is selected as one of evolutionary algorithms. Each solution in the GA is encoded by a simple indirect encoding, namely a giant tour. The giant tour is encoded as a sequence, e.g., a permutation of all nodes. A certain number of routes (m) can then be extracted from the giant tour based on the order of the visited nodes in the sequence and the constraints. Three different moves: Shift, Swap, and Destruct-repair are used as mutation operators. Shift corresponds to the earlier explained Relocate, but now implemented on the giant tour. For each node it is checked if a better position in the giant tour can be found. In Swap, illustrated in Fig. 5.14, an exchange of all couples of two different nodes in the giant tour is evaluated. Destruct-repair is done by removing a small part of the giant tour sequence with a view to rebuilding an improved solution.

A small number of solutions in the initial population is built by an Iterative Destruction/Construction Heuristic (IDCH) and the rest is generated randomly. New chromosomes are evaluated using the Optimal Splitting procedure. The population is a set of chromosomes for which two criteria are evaluated: the profit and the total travel cost. At the end of the search, the chromosome with the highest profit is treated as the best solution.

Various population-based algorithms based on PSO have been proposed to solve the TOP. We will discuss the latest PSO, namely PSO-inspired algorithm (PSOiA). As explained in Sect. 5.3.2, PSO is a swarm intelligence algorithm with the basic idea of simulating the collective behavior of swarms in nature. Each particle in the swarm has a small probability to be relocated to a completely new position and it also has a probability to be further improved through a local search process. The concept of the giant tour and some of the above-mentioned local search moves are implemented.

Also, a combination of Simulated Annealing and a multi-start hill climbing strategy is able to solve the TOP. The multi-start hill climbing strategy is implemented in order to escape from local optima. Simulated Annealing begins with a randomly generated initial solution. At each iteration, it selects a new solution from the neighborhood of the current solution. A worse solution can be accepted with a small probability. Local search moves, such as swap and insert, are implemented in order to further improve the quality of the solution.

The last algorithm, Guided Local Search (GLS), combines different local search moves to solve both the OP and the TOP. First, all nodes that cannot be reached anyway are removed from the instance. Then, each route is assigned to one of the nodes which are furthest from the start and end nodes.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.